The seeds are sprouting

Problem
Code

I liked today. It's a combination of relatively gnarly parsing (two big sections with bespoke formats), state machines, and recursion. Fun stuff!

The parsing itself is a big part of the first part, and a big part of parsing is choosing the representation you're parsing into; I went with this:

type Branch<'a> = (Option<(usize, Ordering, i64)>, &'a str);
type Flows<'a> = HashMap<&'a str, Vec<Branch<'a>>>;
type Thing = [i64; 4];

fn parse(input: &str) -> (Flows, impl Iterator<Item = Thing> + '_)

Each workflow is a name, plus a list of branches. The final branch has no condition, so I made the condition optional. Parsing returns a HashMap that maps the workflow name to its conditions, in order.

With all that, checking whether a Thing is accepted or not is a short loop:

let mut flow = "in";
let mut accepted = None;
loop {
	(flow, accepted) = resolve_flow(&flows, flow, &thing);
	if let Some(v) = accepted {
		return v.then(|| thing.into_iter<i64>();
	}
}

fn resolve_flow<'a>(flows: &Flows<'a>, flow: &str, thing: &Thing) -> (&'a str, Option<bool>) {
    for &(check, target) in &flows[flow] {
        let target = match check {
            Some((i, order, n)) => {
                if thing[i].cmp(&n) == order {
                    target
                } else {
                    continue;
                }
            }
            None => target,
        };

        return match target {
            "A" => ("", Some(true)),
            "R" => ("", Some(false)),
            target => (target, None),
        };
    }

    unreachable!()
}

This whole thing is a state machine, where workflows are the nodes; and the branches are transitions between nodes.

I'm pretty happy with thing[i].cmp(&n) == order. order is an Ordering, which is what is returned by comparisons in Rust. It can be Less, Equal, or Greater. During parsing, I convert <s to Less, and >s to Greater, so that I can check whether the condition is fulfilled with that oneliner. Pretty neat.

Part 2 actually reminded me of day 5, hence the title of this post. The core idea is that instead of operating on any single Thing, we instead operate on ranges of values.

fn count_accepts(flows: &Flows, flow: &str, mut ranges: [(i64, i64); 4]) -> i64 {
    let mut result = 0;
    for &(check, target) in &flows[flow] {
        let new_ranges = match check {
            Some((i, order, n)) => {
                let mut sub_ranges = ranges;
                match order {
                    Ordering::Less => {
                        ranges[i].0 = n;
                        sub_ranges[i].1 = n - 1;
                    }
                    Ordering::Greater => {
                        ranges[i].1 = n;
                        sub_ranges[i].0 = n + 1;
                    }
                    Ordering::Equal => unreachable!(),
                }
                sub_ranges
            }
            None => ranges,
        };

        result += match target {
            "A" => new_ranges
                .into_iter()
                .map(|(lo, hi)| 0.max(1 + hi - lo))
                .product(),
            "R" => 0,
            target => count_accepts(flows, target, new_ranges),
        };
    }
    result
}

It looks gnarly, but it's not that bad overall. Our ranges start as four times 1..=4000, as given in the puzzle description. Then, for each branch of the workflow we're given:

• split our set of values ranges into two sets. Ones that fulfill the condition, and ones that don't;
• for the part that fulfills the condition, count the number of elements that got accepted (recursively);
• the part that didn't fulfill the condition moves on to the next condition.
  Because the last condition always applies, this way we eventually cover all 4000^4 combinations.

Very clean task with a couple gnarly implementation bits. Solid 19th day.